package org.lep.leetcode.minimumdepthofbinarytree;

/**
 * Source : https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
 *
 * Created by lverpeng on 2017/8/14.
 *

 * Given a binary tree, find its minimum depth.
 *
 * The minimum depth is the number of nodes along the shortest path from the root node
 * down to the nearest leaf node.
 */
public class MinimumDepth {

    /**
     * 求出一棵二叉树的最小高度
     *
     * @param root
     * @return
     */
    public int minDepth (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.leftChild);
        int right = minDepth(root.rightChild);
        if (left > right) {
            return right + 1;
        } else {
            return left + 1;
        }
    }


    public TreeNode createTree (char[] treeArr) {
        TreeNode[] tree = new TreeNode[treeArr.length];
        for (int i = 0; i < treeArr.length; i++) {
            if (treeArr[i] == '#') {
                tree[i] = null;
                continue;
            }
            tree[i] = new TreeNode(treeArr[i]-'0');
        }
        int pos = 0;
        for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
            if (tree[i] != null) {
                tree[i].leftChild = tree[++pos];
                if (pos < treeArr.length-1) {
                    tree[i].rightChild = tree[++pos];
                }
            }
        }
        return tree[0];
    }


    private class TreeNode {
        TreeNode leftChild;
        TreeNode rightChild;
        int value;

        public TreeNode(int value) {
            this.value = value;
        }

        public TreeNode() {

        }
    }

    public static void main(String[] args) {
        MinimumDepth minimumDepth = new MinimumDepth();
        char[] arr0 = new char[]{'#'};
        char[] arr1 = new char[]{'3','9','2','#','#','1','7'};
        char[] arr2 = new char[]{'3','9','2','1','6','1','7','5'};

        System.out.println(minimumDepth.minDepth(minimumDepth.createTree(arr0)));
        System.out.println(minimumDepth.minDepth(minimumDepth.createTree(arr1)));
        System.out.println(minimumDepth.minDepth(minimumDepth.createTree(arr2)));
    }
}
